/*
 * Huffman.h
 *
 *  Created on: 2011-4-6
 *      Author:蓝达斌
 *
 *   Copyright   : Copyright © 2011 Binda&Aeolus
 All Rights Reserved
 */

#ifndef HUFFMAN_H_
#define HUFFMAN_H_
#include <string.h>
#include <malloc.h>
#include <iostream>
using namespace std;
typedef struct {

	unsigned int weight;
	unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree;//动态分配数组存储哈夫曼树

typedef char ** HuffmanCode;//动态分配数组存储哈夫曼编码表

//选择HT[1...i-1] parent为0且weight最小的两个节点,其序号分别为s1,s2;
void Select(HuffmanTree &HT, int k, int &s1, int &s2) {

	unsigned int minx=100000,miny=100000;
	for(int i=1; i<=k;i++)
	{
		if(HT[i].parent ==0)
		{
			if(HT[i].weight < minx)
			{
				minx = HT[i].weight;
				s1 = i;
			}
		}
	}
	for(int i=1; i<=k;i++)
	{
		if(i!=s1 && HT[i].parent ==0)
		{
			if(HT[i].weight < miny)
			{
				miny = HT[i].weight;
				s2 = i;
			}
		}
	}

	/*int initial=1;
	for (int i = 1; i<=k; i++) {
		if (HT[i].parent == 0) {
             s1=i;
             initial=i;
             break;
		}
	}
	for(int i=initial+1;i<=k;i++)
	{  if(HT[i].parent==0)
	     if (HT[i].weight < HT[s1].weight)
			{s1 = i;
	         initial=i;
	        }
	}
	//s1 min
	for (int i = 1; i<=k; i++) {
			if (HT[i].parent == 0&&i!=s1) {
	             s2=i;
	             initial=i;
	             break;
			}

		}
    for(int j=s2;j<=k;j++)
    {
    	if(HT[j].parent==0&&j!=s1&&j!=s2)
    	 if (HT[j].weight-HT[s1].weight< HT[s2].weight-HT[s1].weight)
    					s2 = j;
    }*/


}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {
	HuffmanTree p;
	if (n <= 1)
		return;
	int m = 2 * n - 1;
	HT = (HuffmanTree) malloc((m + 1) * sizeof(HTNode));//0号单元未用
	int i;
	for (i = 1, p = HT + 1; i <= n; ++i, ++p, ++w) {
		p->weight = *w;
		p->lchild = 0;
		p->rchild = 0;
		p->parent = 0;
	}//初始化叶子节点，并赋权值; (1~n节点)

	for (;i<= m;++i, ++p) {
		p->weight = 0;
		p->lchild = 0;
		p->rchild = 0;
		p->parent = 0;
	} //其余节点赋值为0

	//构造哈夫曼树
	int s1, s2;
	for (int i = n + 1; i <=m; ++i) {

		Select(HT, i - 1, s1, s2);//选择HT[1...i-1] parent为0且weight最小的两个节点,其序号分别为s1,s2;
		//cout << "select the 2 leaves :"<<s1 << "&" << s2 << endl;
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lchild = s1;
		HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
	//从叶子到根逆向求每个字符的哈夫曼编码
	HC = (HuffmanCode) malloc((n + 1) * (sizeof(char*)));
	char *cd = (char*) malloc(n * sizeof(char));
	cd[n - 1] = '\0';
	for (int i = 1; i <= n; ++i) {
		int start = n - 1;
		for (int c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) {
			if (HT[f].lchild == c)
			{	cd[--start]='0';//cout<<"0";
			}
			else
			{	cd[--start]='1';//cout<<"1";
			}
			 HC[i]=(char*)malloc((n-start)*sizeof(char));
			 strcpy(HC[i],&cd[start]);
		}

	}
	free(cd);

}


#endif /* HUFFMAN_H_ */
